//#include <iostream>
//
//using namespace std;
//typedef long long LL;
//int n, p;
//const int N = 1e4;
//LL f[N][N];
//void get_C()
//{
//	for (int i = 0; i <= n; i++)
//	{
//		f[i][0] = 1;
//		for (int j = 1; j <= i; j++)
//		{
//			f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
//		}
//	}
//}
//int main()
//{
//	get_C();
//	return 0;
//}

#include <iostream>

using namespace std;
typedef long long LL;
int n, m, k;
const int N = 2010;
int f[N][N];
int g[N][N];
	
void init()
{
	for (int i = 0; i <= 2000; i++)
	{
		f[i][0] = 1;
		for (int j = 1; j <= i; j++)
		{
			f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % k;
			g[i][j] = g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1] + (f[i][j] == 0);
		}
		g[i][i + 1] = g[i][i];
	}
}
int main()
{
	int T; cin >> T >> k;
	init();
	while (T--)
	{
		cin >> n >> m;
		cout << g[n][min(n, m)] << endl;
	}

	return 0;
}